package com.dyz.leetcode._08_StackAndQueue;

import java.util.ArrayDeque;
import java.util.TreeMap;

public class _456_find132pattern {
    //暴力解法
    public boolean find132pattern3(int[] nums) {
        int n = nums.length;
        if (n < 3) {return false;}
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                for (int k = j + 1; k < n; k++) {
                    if (nums[i] < nums[k] && nums[k] < nums[j]) {
                        return true;
                    }
                }
            }
        }
        return false;
    }

    //线性查找  超时
    public boolean find132pattern2(int[] nums) {
        if(nums==null || nums.length<3){return false;}

        int numsi = nums[0];
        for(int j=1; j<nums.length; j++){
            for(int k=j+1; k<nums.length; k++){
                if(numsi<nums[k] && nums[k]<nums[j]){return true;}
            }
            numsi = Math.min(numsi, nums[j]);
        }
        return false;
    }

    //线性+红黑树
    public boolean find132pattern1(int[] nums) {
        if(nums==null || nums.length<3){return false;}
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int k=2; k<nums.length; k++){
            map.put(nums[k], map.getOrDefault(nums[k], 0)+1);
        }

        int numsi = nums[0];
        for(int j=1; j<nums.length-1; j++){
            if (nums[j] > numsi) {
                // 红黑树查找大于左边最小值(numsi)得元素
                Integer numsk = map.ceilingKey(numsi + 1);
                if (numsk != null && numsk < nums[j]) {return true;}
            }
            numsi = Math.min(numsi, nums[j]);
            // 将下一个元素从右边的集合中删除掉
            map.put(nums[j + 1], map.get(nums[j + 1]) - 1);
            if (map.get(nums[j + 1]) == 0) {map.remove(nums[j + 1]);}
        }
        return false;
    }

    //使用栈
    public boolean find132pattern(int[] nums) {
        int n = nums.length;
        if(n<3){return false;}

        //维护一个前缀最小值数组，用于确定nums[i]
        int[] minPrefix = new int[nums.length];
        minPrefix[0] = nums[0];
        for (int i = 1; i < nums.length ; i++) {
            minPrefix[i] = Math.min(minPrefix[i - 1], nums[i]);
        }

        ArrayDeque<Integer> stack = new ArrayDeque<>();
        stack.push(nums[n-1]);
        for (int j = n-2; j >=1 ; j--) {
            if(nums[j]>minPrefix[j]) {
                while (!stack.isEmpty() && stack.peek() <= minPrefix[j]) {
                    stack.pop();
                }
                if (!stack.isEmpty() && stack.peek() < nums[j]) {
                    return true;
                }
                stack.push(nums[j]);
            }
        }
        return false;
    }

}
